package week_09;

import java.util.*;

/**
 * 127. 单词接龙
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
 * <p>
 * 序列中第一个单词是 beginWord 。
 * 序列中最后一个单词是 endWord 。
 * 每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典 wordList 中的单词。
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
 * 找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：5
 * 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：0
 * 解释：endWord "cog" 不在字典中，所以无法进行转换。
 */
public class WordLadder_127 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> dist = new HashMap<>();
        final int E = (int) 1e9;
        Set<Character> cset = new HashSet<>();
        for (String s : wordList) {
            dist.put(s, E);
            for (char c : s.toCharArray()) cset.add(c);
        }


        // wordList => hash 值
        // 每转换一次word单词就需要验证hash值是否有
        int ans = 0;
        if (!dist.containsKey(endWord)) return ans;

        Deque<String> fdeque = new LinkedList<>();
        Deque<String> ldeque = new LinkedList<>();
        dist.put(beginWord, 1);
        dist.put(endWord, 1);
        fdeque.add(beginWord);
        ldeque.add(endWord);
        while (!fdeque.isEmpty() || !ldeque.isEmpty()) {
            String head = fdeque.getFirst();
            String tail = ldeque.getFirst();
            /**
             *
             */

            char[] hChars = head.toCharArray();
            for (int i = 0; i < hChars.length; i++) {
                for (char c : cset) {
                    if (hChars[i] != c) {
                        hChars[i] = c;
                        String next = String.valueOf(hChars);
                        if (dist.containsKey(next)) {
                            if (dist.get(next) < E) {
                                return dist.get(head) + dist.get(next);
                            } else {
                                dist.put(next, dist.get(head) + 1);
                                fdeque.offer(next);
                            }
                        }
                    }
                }
            }

            char[] tChars = tail.toCharArray();
            for (int i = 0; i < tChars.length; i++) {
                for (char c : cset) {
                    if (tChars[i] != c) {
                        tChars[i] = c;
                        String next = String.valueOf(tChars);
                        if (dist.containsKey(next)) {
                            if (dist.get(next) < E) {
                                return dist.get(tail) + dist.get(next);
                            } else {
                                dist.put(next, dist.get(tail) + 1);
                                ldeque.offer(next);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        String[] wordList = new String[]{"hot", "dot", "dog", "lot", "log", "cog"};

        WordLadder_127 test = new WordLadder_127();
        int ans = test.ladderLength(beginWord, endWord, Arrays.asList(wordList.clone()));
        System.out.println(ans);
    }

}
